package alogrithm;

import java.util.Arrays;

/**
 * @author lbw
 * @version 1.0
 * @date 2021/8/16 20:26
 */
public class QuickSort {

    public static void main(String[] args) {
        int[] a = new int[]{3, 2, 6, 7, 5, 8, 1};
        // {1 , 2, 3},{ 5, 6 ,7, 8};
        quickSort(a, 0, a.length - 1);
        System.out.println(Arrays.toString(a));

    }

    public static void quickSort(int[] nums, int l, int r) {

        if (l > r) return;

        int low = l;
        int high = r;
        int pivot = nums[l];

        while (low < high) {
            while (low < high && nums[high] >= pivot) {
                high--;
            }

            while (low < high && nums[low] <= pivot) {
                low++;
            }

            if (low < high) {
                swap(nums, low, high);
            }
        }

        nums[l] = nums[low];
        nums[low] = pivot;

        quickSort(nums, l, low - 1);
        quickSort(nums, low + 1, r);
    }

    public static void swap(int[] nums, int a, int b) {
        int temp = nums[a];
        nums[a] = nums[b];
        nums[b] = temp;
    }
}
